1. Field of the Invention
The invention relates generally to techniques for embedding information in digital representations and more particularly to techniques for embedding information that have reduced computational costs.
2. Description of Related Art
Digital watermarking is a technique for embedding information in a digital representation which remains invisible when the digital data is used to produce an analog output such as an image, a video display, sound, or a printed document. The information remains invisible to the person perceiving the analog output because it is added to the digital data in such a fashion that it becomes part of the noise that is an inevitable part of any analog output. To give a simple example: the digital representations of gray-scale pictures are made up of pixels whose values represent black, white, and a range of grays between black and white. Small changes in the values of individual pixels in the gray scale image will not be perceptible to the viewer when the image is displayed or printed. To make a digital watermark in the image, one need only add a pattern of such small changes to the digital representation. To read the watermark in the digital representation, one need only know what pixels are part of the pattern, what changes were made, and how these changes are to be interpreted. The pattern may represent a message, for example, the name of the owner of the copyright in the image, it may simply serve to detect copying or alteration of the image, or it may uniquely identify the image, or it may do some or all of these things at once. In the broadest sense, a watermark may be any information which is added to a digital representation that does not affect the manner in which the digital representation functions. For example, a word processing document may be watermarked by slightly altering the manner in which particular lines of the document are justified, or program code may be watermarked by making a change which does not affect the program code's function, for example, by adding a function which does nothing. In the following, the term watermark is to be understood in this broadest sense, as well as in its more traditional sense of information that is hidden in the digital representation.
The use of watermarking to uniquely identify a digital representation is termed digital fingerprinting, the watermark itself is termed a fingerprint, and a digital representation that contains a fingerprint is termed a fingerprinted digital representation. Because a fingerprinted digital representation is uniquely identified by its fingerprint, the fingerprint can be used to relate the digital representation to a specific transaction. For example, if the fingerprint in a fingerprinted digital representation relates the fingerprinted digital representation to a particular customer and a digital representation with the same fingerprint appears elsewhere, it is clear that the fingerprinted digital representation has been misappropriated and depending on the circumstances, the customer may be held liable for the misappropriation.
Widespread use of fingerprinted digital representations has been hindered by the computational cost of individually watermarking multiple copies of a digital representation. The computational cost is particularly important where digital representations are being streamed on demand across a network to a consuming device such as a PC or a digital video or audio device. When a digital representation is being streamed to a consuming device, the consuming device does not download the complete digital representation and then begin processing the digital representation, but instead starts processing the digital representation as soon as it receives the first part of it and continues processing the digital representation as it receives it. Streaming has two advantages: it reduces the delay before the consuming device can begin processing the downloaded data and thus playing music or displaying a video and it greatly reduces the amount of memory required in the consuming device, since the consuming device need not store the entire digital representation. Of course, the larger the digital representation, the more important these advantages become.
The computational cost of fingerprinting streaming digital representations is important because making the fingerprint reduces the speed with which a fingerprinted copy can be made and thus increases the time to respond to the user's request for the streamed copy. Components of the computational cost include the large size of the representations, which require the alteration of many bits, and the computational costs of the cryptographic techniques used to hide the fingerprints. The fingerprint must of course be hidden because it could otherwise be removed when the digital representation was misused. Even where the copy is not being streamed, the computational cost may be important in any situation where large numbers of uniquely identified copies are being distributed via the network. Virtually any kind of digital data may be fingerprinted. Examples are copies of digital representations of still images, program code, plain text, or formatted text.
Use of watermarks generally in streaming data has been hindered by the fact that many kinds of streaming data are encoded or compressed from a digital original into a format such MPEG-1, 2, or 4 for video or MPD for audio. Any watermark applied to the digital original is seriously damaged in the encoding and/or compression processes, while applying the watermark to the encoded or compressed version of the original has the problems of computational cost mentioned above.
It is thus an object of the invention disclosed herein to reduce the computational cost of fingerprinting or otherwise marking a copy of a digital representation.